1. Field of the Invention
This invention relates generally to the field of adaptive equalizers and more particularly, to adaptive equalizers for reducing multipath effects and self-noise and increasing convergence speed when used in wireless data transmission environments.
2. Description of the Prior Art
Equalizers are frequently used to correct channel linear distortion. In a wireless channel, linear distortions frequently include multipath and fading. This is due to the fact that the received signals often include signal components that are multiply reflected in addition to the line-of-sight signal from the transmitter. Quite often, these multiply reflected signal components do not have constant signal strengths relative to the line-of-the sight signal, or between themselves. These cause fading in the received signal.
Multipath causes fluctuations in channel frequency responses. Fading further makes these fluctuations time varying.
Adaptive equalizers and adaptive decision feedback equalizers are often used to combat these fluctuations in channel frequency responses. For further details of such equalizers, the reader is directed to following references: “Adaptive Filter Theory”, Fourth Edition by Simon Haykin, Prentice Hall, 2002 and “Digital Communications”, Fourth Edition by John G. Proakis, McGraw-Hill, 2001.
An adaptive finite impulse response (FIR) equalizer, with length N, using Least Mean Square (LMS) update criteria works in the following manner.
With reference to FIG. 1, a conventional LMS equalizer 100 is shown to receive an input signal sample sequence {vn}, create multiply delayed versions of the signal samples by delay elements 110, then multiply these multiply delayed signal samples by a set of equalizer coefficients c0, . . . , cN−1 131, where N is equalizer length. The results are then summed together, by a summer 115, to form an equalizer filter output sequence {yn}. This is shown in the following Filter Equation:
                              y          n                =                              ∑                          i              =              0                                      N              -              1                                ⁢                                    v                              n                -                i                                      ⁢                          c              i                                                          Eq        .                                  ⁢                  (          1          )                    
The output from the equalizer, which is the equalizer filter output sequence {yn}, generated by Eq. (1), then goes through a decision device Q 140 to generate the equalizer decision sequence {dn}. The equalizer decision together with equalizer filter output is used to produce the equalizer error sequence {en} by a difference operator 160 according to Error Equation:en=dn−yn  Eq. (2)
The equalizer error is further scaled by a step size multiplier 150 to form scaled equalizer error. The coefficients of the equalizer are then updated by an update means 120 using the scaled equalizer error and delay line data (from the delay line block 110) according to the Update Equation:cik+1=cik+Δenvn−i, i=0, . . . , N−1  Eq. (3)Where vn−i's are equalizer delay line signal samples, en is equalizer error, and Δ is step size for equalizer coefficients update. cik's (same as ci's) and cik+1's are current set and next set of equalizer coefficients.
FIG. 2 shows a higher level block diagram of the equalizer 100 of FIG. 1 wherein an equalizer filter and update block 290 includes a delay block 240, which is the same as the delay elements 110 in FIG. 1, Equalizer Filter block 210 is the same as multiplying by the set of equalizer coefficients c0, . . . , cN−1 and summation 130 of FIG. 1, the coefficient update block 230 is the same as the update means 120 of FIG. 1. The decision device Q 220 is the same as the decision device Q 140 of FIG. 1 and the difference operator for error formation 260 and error multiplier 250, by step size, are the same as 160 and 150, respectively in FIG. 1.
An adaptive decision feedback equalizer (DFE) using LMS update criteria works in a similar way. Now, the three key equations corresponding to Eqs. (1)-(3) are as following for time index n:
Filter Equation:
                              y          n                =                                            ∑                              i                =                0                                            N                -                1                                      ⁢                                          v                                  n                  -                  i                                            ⁢                              c                i                                              +                                    ∑                              i                =                1                            B                        ⁢                                          d                                  n                  -                  i                                            ⁢                              b                i                                                                        Eq        .                                  ⁢                  (          4          )                    Error Equation:en=dn−yn  Eq. (5)Update Equations:cik+1=cik+Δffenvn−i, i=0, . . . , N−1  Eq. (6)bkk+1=bik+Δfbendn−i, i=1, . . . , B  Eq. (7)Where N is equalizer length for the feedforward part, B is equalizer length for the feedback part, vn−i's are equalizer delay line samples, dn−i's are delayed equalizer decisions, ci's are equalizer feedforward coefficients, bi's equalizer feedback coefficients, en is equalizer error, and Δff and Δfb are coefficients updates step sizes for feedforward and feedback parts respectively. cik's (same as ci's), bik's (same as bi's) and cik+1's, bik+1's are current and next sets of equalizer feedforward and feedback coefficients.
FIG. 3 shows an exemplary conventional decision feedback equalizer 300 including a decision feedback equalizer filter and update block 330 and a feedforward filter and update block 320. The decision feedback equalizer filter and update block 330 is shown to perform filter function, which is performed by the DFE Filter 302 using feedback coefficients from a decision feedback equalizer coefficient update function 304 and the previous equalizer decision outputs {dn} stored in delay line 303. The block 304 is shown to update equalizer feedback coefficients using equalizer error {en} scaled by a feedback step size Δfb using multiplier 306 as well as previous output of the equalizer decision stored in delay line 303. The feedforward filter and update block 320 similar to block 290 of FIG. 2 is shown to perform filter function by FFE filter 312 using sample inputs {vn} stored in Delay Line 313, and feedforward coefficients from a FFE Update block 314. The feedforward equalizer update block 314 is similar to the block 230 of FIG. 2 for updating equalizer feedforward coefficients.
A feedforward step size multiplier 308 provides scaled equalizer error by feedforward step size Δff to the coefficient update function 314. Similarly, the feedforward filter block 312 is similar to the block 210 of FIG. 2 and its output is provided to a summer 316 for a summation operation with the output of the block 330 and the result of the summation operation, at the output of the summer 316, represented by {yn}, is provided to a equalizer decision block Q 310, which is similar to the block 220 of FIG. 2. The output of the summer 316 is also provided to a difference operator 318 to produce equalizer error {en}. Eq. (4) is implemented by function 312 in block 320, function 302 in block 330 and summer 316, Eq. (5) is implemented by the difference operator 318, Eq. (6) is implemented by the function 314 in block 320, and Eq. (7) is implemented by function 304 in block 330.
When input signal sample data {vn} are sampled at symbol clock rate, the equalizer is called symbol spaced equalizer. When data {vn} are sampled at a clock rate faster than symbol clock, it is called fractionally-spaced equalizer. The sample data, equalizer decisions, and coefficients, can be real or complex.
Besides LMS coefficients updating scheme, there are other coefficients updating schemes such as zero-forcing (ZF), recursive least square (RLS), etc.
After initial convergence, an equalizer needs to continuously update its coefficient to track possible changes in channel response. In multipath and fading environment, channel response can change quite fast.
In the current field of the art, equalizers are typically implemented using devices with finite operating precision in its delay line samples and coefficients. The equalizer typically has finite precision in its filtering and updating operations including multiply-and-accumulation (MAC). This problem of finite precision implementation creates additional noise at the equalizer filter output. This noise is called quantization noise.
During the initial convergence stage and later tracking stage, the equalizer coefficients are moving around their theoretical optimal values. Because of this variation and deviation from their optimal values, the performance of the equalizer differs from its optimal value. This non-optimal feature creates another additional noise at the equalizer filter output. This noise is called self-noise for the equalizer.
Self noise and quantization noise are the two noise factors that reduce the equalizer performance from the theoretically achievable optimal equalizer performance. They affect both initial convergence and steady state performances.
The performance requirement of an adaptive equalizer depends on the channel conditions, output signal to noise ratio (SNR) requirement, as well as converging speed requirement. These requirements determine equalizer length, updating step sizes, and the precisions of its coefficients as well as filter operations. All of these directly affect the cost of implementing the equalizer.
The equalizer's length determines its time span. On one hand, a longer equalizer gives better theoretic steady state performance assuming the coefficients reached their theoretical optimal state. On the other hand, a longer adaptive equalizer requires a smaller step size under the same channel condition. A smaller step size normally results in slower converging speed. Therefore a longer adaptive equalizer has slower converging speed.
For the same step size and channel condition, a longer equalizer generates more self-noise because more coefficients are in non-optimal state.
A longer equalizer also requires larger precision in its coefficients and operations. This is because each of the quantized coefficients and operations contributes a little to the equalizer's quantization noise, and the total contribution to the quantization noise due to coefficient and operation quantization is the sum of each individual contribution. Therefore, in a conventional equalizer structure, the longer the equalizer is, the more severe the quantization noise becomes for the same individual coefficient and operation quantization level. Equivalently, to keep the overall quantization noise level to a desired level, higher coefficient and operation precision is required for a longer equalizer.
A known scheme referred to as Block Floating Point (BFP), as discussed in the publication “Implementation Options for Block Floating Point Digital Filters” by K. Raley and P. Bauer, 1997 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP'97)—Volume 3 p. 2197, is intended to mitigate the impact of finite precision operations and quantization in data and coefficients. For a true floating point data representation, a value is represented as a mantissa part and an exponent part to represent values with large dynamic range with reasonable quantization precision. BFP uses an exponent for a block of values to achieve similar advantage. BFP essentially use a dynamic scaling for a block of data before quantization to improve the quantization performance.
When an equalizer is implemented in BFP with block size L and number of blocks M, the set of adaptive equalizer equations corresponding to Eqs. (1)-(3) for time index n become:
Filter Equation:
                              y                      n            ,            m                          =                              ∑                          i              =              0                                      L              -              1                                ⁢                                    v                                                n                  -                  i                                ,                m                                      ⁢                          c                              i                ,                m                            ′                                                          Eq        .                                  ⁢                  (          8          )                    
The outputs from all blocks are combined using Combination Equation, Eq. (9):
                              y          n                =                              ∑                          i              =              0                                      M              -              1                                ⁢                                                    y                                  n                  ,                  m                                            ⁡                              (                                  a                                      j                    m                                                  )                                                    -              1                                                          Eq        .                                  ⁢                  (          9          )                    Where c′i,m=ci,majm, a is the base for the BFP operation, jm is the exponent part for block m, and ajm is the equivalent scaling for block m, and its inverse (ajm)−1's is the combination weighting for block m in forming the equalizer output.
The coefficients Update Equation becomes:c′i,mk+1=c′i,mk+Δajmenvn−i, i=0, . . . , L−1, m=0, . . . , M−1  Eq. (10)
During the initial convergence and later on tracking, jm's are varying, therefore corresponding monitoring and changing in those equations are necessary.
In general, an equalizer implemented using BFP has better trade off between cost and quantization noise. This approach often leads to a lower overall implementation cost of an adaptive equalizer for the desired quantization noise performance. However, because the effect of Eqs. (8)-(10) are mathematically equivalent to Eqs. (1),(3) except in numerical system representation, the dynamic behavior of an adaptive equalizer implemented using BFP is not changed. Specifically, BFP implementation does not affect the equalizer's self noise, converging speed, or tracking behavior.
In the multipath environment, only some of the equalizer coefficients have significant values and others have zero or near zero values. Fading further makes the values and the locations of those significant coefficients time varying. Over time, some of the previously significant coefficients may become zero or near zero and new significant coefficients may emerge.
For conventional equalizers implementation, these features of multipath and fading environment are not utilized. The equalizers' behavior in converging speed and self-noise are not affected by multipath and fading. This also includes the equalizers implemented using BFP even though such equalizers using BFP might have improved the equalizers' quantization behavior.
Sparse equalizers, discussed in U.S. Pat. No. 5,777,910, entitled “Sparse equalization filter adaptive in two dimensions” issued on Jul. 7, 1998 to Cheng-Youn Lu, are introduced to combat problems associated with conventional equalizers. An example of a conventional sparse decision feedback equalizer 400 is provided, in block diagram form, in FIG. 4. A sparse equalizer tries to concentrate its coefficients to a set of effective coefficient locations that have significant values, and remove all “near zero” coefficients. In FIG. 4, this is done by use of the switches 402 and 408, controlled by switch control block 420. The purpose of switches 402 and 408 is to select only those delayed data from FFE Delay 401 and DFE Delay 407 that correspond to the significant equalizer coefficients. Only the significant equalizer coefficients are implemented and therefore effective. All other coefficients are set to zero and not implemented. Doing so reduces the number of required coefficients because the FFE filter block 403 and the FFE update block 404 as well as the DFE filter block 409 and the DFE update block 410 only need to process the effective coefficients, therefore, at least in theory, there is a reduction of the converging speed, self noise, and quantization noise problems mentioned above. These features of the sparse equalizer make it particularly suitable for stationary multipath environment where relatively few effective coefficients are required and the locations of those effective coefficients do not change quickly. A sparse equalizer with relatively few effective coefficients should, at least in theory, behave like a smaller equalizer. So the problems in converging speed, quantization noise, and self noise are all improved compared with a conventional equalizer with the same time span. At the same time, the total implementation cost of a sparse equalizer may also be smaller compared with a conventional equalizer with the same time span.
Two schemes are needed to implement a sparse equalizer, which is discussed in the Cheng-Youn Lu reference, indicated above. One scheme, not shown in FIG. 4, is to determine where to allocate the effective coefficients, and the other scheme is to implement switching mechanisms shown as 402 and 408 to apply those effective coefficients to generate an equalizer output.
The first scheme requires one to either sequentially learn the locations of those effective coefficients or to periodically initialize those effective locations using some training sequence. Sequentially learning the effective locations will significantly slow down the convergence and tracking behavior of the equalizer. Periodical initialization using a training sequence reduces the effective channel bandwidth, adds additional costs to implementation of the equalizer, and reduces the tracking capability and overall performance if the channel changes between training sequences. Both approaches of selecting the effective coefficient locations involve additional cost compared with conventional equalizer implementations.
The second scheme requires significantly adding complexity in the equalizer's implementation. Suppose the equalizer has 500 total possible locations for the coefficients yet there are 100 effective coefficients, then the equalizer needs a circuit that can dynamically switch the 100 effective coefficients into any 100 of those 500 locations. This requirement on dynamic switching capability together with the requirement on selecting effective coefficient locations significantly offsets cost savings due to a reduced number of effective coefficients.
Fading in a multipath environment further complicates the problem for sparse equalizers. For it now has to dynamically allocate its coefficients. Fading causes the signal strength to change in both absolute terms and in relative terms between each signal path of the multipath signal. When the multipath environment changes, the effective coefficient allocations have to change accordingly and immediately. Otherwise, the sparse equalizer suffers significant performance loss.
Because a sparse equalizer has to either periodically re-allocate its coefficients or sequentially try each of the possible locations to see whether or not significant equalizer coefficients are needed in those locations, both of these methods significantly slow down the tracking ability of a sparse equalizer. Therefore, a sparse equalizer performs inadequately in combating dynamic multipath and fading channel, and at the same time adds to the cost of implementation of an equalizer.
Therefore, for the foregoing reasons, the need arises for an adaptive equalizer having fast convergence time, low self-noise and lower implementation or manufacturing costs.